#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
typedef struct btnode
{
	char data;
	struct btnode* plch;
	struct btnode* prch;
}btd;
typedef struct node
{
	struct btnode* data;
	struct node* next;
}nd;
typedef struct linkqueue
{
	nd* f;
	nd* r;
}lq;
lq* queueInit()
{
	lq* p = (lq*)malloc(sizeof(lq));
	if (p == NULL)
	{
		printf("malloc fail");
		return NULL;
	}
	p->f = (nd*)malloc(sizeof(nd));
	if (p->f == NULL)
	{
		free(p);
		return NULL;
	}
	p->r = p->f;
	p->f->next = NULL;
	return p;
}
bool is_empty(lq* p)
{
	if (p->f == NULL && p->r == NULL)
		return true;
	else
		return false;
}
bool enqueue(lq* p, btd* d)
{
	nd* newnode = (nd*)malloc(sizeof(nd));
	if (newnode == NULL)
	{
		printf("malloc fail");
		return false;
	}
	newnode->data = d;
	newnode->next = NULL;
	p->r->next = newnode;
	p->r = newnode;
	return true;
}
bool outqueue(lq* p, btd** val)
{
	if (is_empty(p))
		return false;
	*val = p->f->next->data;
	nd* tmp = p->f->next;
	p->f->next = tmp->next;
	if (p->f->next == NULL)
		p->r = p->f;
	tmp->next = NULL;
	free(tmp);
	return true;
}
btd* create_bree()
{
	btd* pa, * pb, * pc, * pd, * pe;
	pa = malloc(sizeof(btd));
	pb = malloc(sizeof(btd));
	pc = malloc(sizeof(btd));
	pd = malloc(sizeof(btd));
	pe = malloc(sizeof(btd));

	pa->plch = pb;
	pa->prch = pc;
	pb->plch = pd;
	pb->prch = pe;
	pc->plch = NULL;
	pc->prch = NULL;
	pd->plch = NULL;
	pd->prch = NULL;
	pe->plch = NULL;
	pe->prch = NULL;
	pa->data = 'a';
	pb->data = 'b';
	pc->data = 'c';
	pd->data = 'd';
	pe->data = 'e';
	return pa;
}
void pre_show(btd* proot)
{
	if (proot != NULL)
	{
		printf("%c ", proot->data);
		if (proot->plch != NULL)
			pre_show(proot->plch);
		if (proot->prch != NULL)
			pre_show(proot->prch);
	}
}
void level_show(btd* proot)
{
	lq* pq;
	pq = queueInit();
	btd* tmp = proot;
	enqueue(pq, tmp);
	while (!is_empty(pq))
	{
		outqueue(pq, &tmp);
		if (tmp != NULL)
		{
			printf("%c ", tmp->data);
			if (tmp->plch != NULL)
				enqueue(pq, tmp->plch);
			if (tmp->prch != NULL)
				enqueue(pq, tmp->prch);
		}
	}
}
int main()
{
	btd* proot = create_bree();
	pre_show(proot);
	printf("\n");
	level_show(proot);
	return 0;
}